import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {

        //杨辉三角
    public static List<List<Integer>> generate(int numRows) {
        // 结果值
        List<List<Integer>> res = new ArrayList<>();
        // 每一行的元素
        ArrayList<Integer> row = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            // 下面一行都会比上面一行多一个元素，我们在第一个位置给他加个1
            row.add(0, 1);
            // 遍历每一行的结果，遍历的时候跳过第一个和最后一个，
            // 每个格子的值都是他正上面和左上角元素的和
            for (int j = 1; j < row.size() - 1; j++)
                row.set(j, row.get(j) + row.get(j + 1));
            // 把结果存放到 res 中
            res.add(new ArrayList<>(row));
        }
        return res;
    }

//合并两个非降序数组之先合并再排序法；
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i=0;i<n;i++){
            nums1[m+i] = nums2[i];
        }
        Arrays.sort(nums1);
    }

    public static void main3(String[] args) {
        int m = 5;
        int n = 5;
        int[] nums1 = new int[]{1,2,2,4,5,0,0,0,0,0};
        int[] nums2 = new int[]{2,6,6,8,9};
        Test test = new Test();
        test.merge(nums1,m,nums2,n);
        System.out.println(Arrays.toString(nums1));
    }

    //    给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
//
//    考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
//
//    更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
//    返回 k 。
    public int removeDuplicates(int[] nums) {
        int k=0;
        for(int i=0;i<nums.length;i++){
            if(nums[k]!=nums[i]){
                nums[++k]=nums[i];
            }
        }
        return ++k;
    }

    public static void main2(String[] args) {
        int[] nums = {1,2,3,4,4,4,7,8,8,10};
        Test test = new Test();
        int ret = test.removeDuplicates(nums);
        System.out.println(ret);
        for (int i = 0; i < ret; i++) {
            System.out.print(nums[i] + " ");
        }
    }

    //    给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
//
//    不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
//
//    元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            if (nums[left] == val) {
                nums[left] = nums[right];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
        //时间复杂度超时
//        int uesdSize = nums.length;
//        for (int i = 0; i < nums.length; i++) {
//            if(nums[i] == val){
//                for (int j = i; j < nums.length-1; j++) {
//                    nums[j] = nums[j+1];
//                }
//                uesdSize--;
//                i--;//数组发生移动，需要重新检索
//            }
//        }
//        return uesdSize;


    public static void main1(String[] args) {
        int[] nums = {1,2,3,4,4,6,7};
        int val = 4;
        Test test = new Test();
        int ret = test.removeElement(nums,val);
        System.out.println(ret);
        for (int i = 0; i < ret; i++) {
            System.out.print(nums[i] + " ");
        }
    }
}
